package com.atwy.linearstructure.stack;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.Stack;

/**
 * RPN，逆波兰表达式，逆波兰记法，后缀表达式
 * 将数据放在前面，运算符放在后面
 * 如：
 * (30+4)*5-6 => 30 4 + 5 * 6 - => 164
 * 4 * 5 - 8 + 60 + 8 / 2 => 4 5 * 8 - 60 + 8 2 / + => 76
 * <p>
 * 后缀表达式可利用栈来进行计算，将表达式解析入栈，然后依次弹出，遇到符号就进行计算
 * 可以进行带()的运算
 * <p>
 * 后缀表达式适合计算式进行计算，但人却不好写出来，尤其是表达式比较长的时候。
 * 但我们可以将 我们熟悉的中缀表达式 转换成 后缀表达式进行计算，这样我们就能通过编程完成复杂计算式的计算
 */
public class ReversePolishNotation {

    public static void main(String[] args) {
        //String express = "4 5 * 8 - 60 + 8 2 / +";
      /*  String express = "30 4 + 5 * 6 -";
        ReversePolishNotation calculator = new ReversePolishNotation();
        List<String> expList = calculator.getListBySplit(express);
        int result = calculator.calculate(expList);
        System.out.println(express + " 计算结果是：" + result);*/

        /*List<String> strings = zhongZhuiExp("(30+4)*(5-6)");
        System.out.println(strings);
        List<String> zhongzhuiExp = doZhongZhuiExp("(30+4)*(5-6)");
        System.out.println(zhongzhuiExp);*/
        String express = "1+((2+3)*4)-5";
        myCalculator(express);

    }


    public static int myCalculator(String express){
        List<String> zhongZhuiExp = doZhongZhuiExp(express);
        System.out.println("中缀表达式是：" + zhongZhuiExp);
        List<String> houZhuiExp = doHouZhuiExp(zhongZhuiExp);
        System.out.println("后缀表达式是：" + houZhuiExp);
        int result = calculate(houZhuiExp);
        System.out.println(express + "=" + result);
        return result;
    }

    /**
     * 根据中缀表达式得到后缀表达式
     * 举例：1+((2+3)*4)-5 => 1 2 3 + 4 * + 5 –
     * 具体逻辑见本包下的 readme.txt
     * 1、如何去掉括号；
     * 2、运算符的计算顺序。
     *
     * @param zhongZhuiExp
     * @return
     */
    public static List<String> doHouZhuiExp(List<String> zhongZhuiExp) {
        // 中缀表达式列表为：[(, 30, +, 4, ), *, (, 5, -, 6, )]
        // 后缀表达式列表为：[30,4,+,5,6,-,*]
        List<String> houZhuiExp = new ArrayList<>();// 后缀表达式存放列表
        // 符号栈
        Stack<String> sign = new Stack<>();

        for (String s : zhongZhuiExp) {
            if (s.matches("\\d+")) {// 匹配数字
                houZhuiExp.add(s);
            } else if ("(".equals(s)) {// 左括号
                sign.push(s);
            } else if (")".equals(s)) {// 右括号
                // 符号栈弹出，直到遇到左括号
                while (!sign.isEmpty()) {
                    String pop = sign.pop();
                    if ("(".equals(pop)) {
                        break;
                    }
                    houZhuiExp.add(pop);
                }
            } else if (isOperation(s)) {// 计算运算符
                if (sign.isEmpty()) {// 符号栈为空时直接放入
                    sign.push(s);
                } else {
                    String peek = sign.peek();
                    if ("(".equals(peek)) {// 符号栈的栈顶是左括号
                        sign.push(s);
                    } else if (compareOper(peek, s) >= 0) { // 比较运算符的优先级，优先级高或者同级都表示栈顶的符号先进行计算
                        houZhuiExp.add(sign.pop());// 弹出栈顶，将栈顶放进后缀表达式列表
                        sign.push(s);// 新符号入栈
                    }
                }

            }
        }
        // 将符号栈里的移到后缀表达式中
        while (!sign.isEmpty()) {
            houZhuiExp.add(sign.pop());
        }

        return houZhuiExp;
    }

    /**
     * 得到中缀表达式
     * 这里用 do-while 比较方便
     *
     * @param express
     * @return
     */
    public static List<String> doZhongZhuiExp(String express) {
        List<String> zhongzhuiExp = new ArrayList<>();
        // (30+4)*(5-6)
        express = express.trim();
        int i = 0;// 指针，用于遍历字符串
        String num = "";// 保存数字
        do {
            char c = express.charAt(i);
            if (isOperator(c)) {
                zhongzhuiExp.add(c + "");
                i++;
            } else {
                // 如果是数字，需要考虑是否是否是多位数字
                num = "";// 置空
                while (i < express.length() && ('0' <= (c=express.charAt(i)) && (c=express.charAt(i)) <= '9')) {
                    num += c;
                    i++;
                }
                zhongzhuiExp.add(num);
            }
        } while (i < express.length());

        return zhongzhuiExp;
    }

    /**
     * 得到中缀表达式
     *
     * @param express
     * @return
     */
    public static List<String> zhongZhuiExp(String express) {
        List<String> zhongzhuiExp = new ArrayList<>();
        express = express.trim();
        int j = -1;
        String num = "";
        for (int i = 0; i < express.length(); i++) {
            char c = express.charAt(i);
            if (isOperator(c)) {
                if (j >= 0 && j < i) {// 说明j开始指向数字
                    num = express.substring(j, i);
                    zhongzhuiExp.add(num);
                }
                // j指向当前操作符的下一位，
                j = i + 1;
                zhongzhuiExp.add(c + "");
            } else {
                if (j < 0) {// 如果表达式最开始是数字时
                    j = i;
                }
                if (i == (express.length() - 1) && (j <= i)) {
                    num = express.substring(j, i + 1);
                    zhongzhuiExp.add(num);
                }
            }
        }
        return zhongzhuiExp;
    }

    public static boolean isOperator(char c) {
        return c == '+' || c == '-' || c == '*' || c == '/' || c == '(' || c == ')';
    }

    public static boolean isOperation(String c) {
        return "+".equals(c) || "-".equals(c) || "*".equals(c) || "/".equals(c);
    }

    /**
     * 比较两个运算符的优先级
     *
     * @param op1
     * @param op2
     * @return =0-同级，>0-op1高于op2,<0-op1低于op2
     */
    public static int compareOper(String op1, String op2) {
        return getPriority(op1) - getPriority(op2);
    }

    /**
     * 给运算符定优先级
     *
     * @param op
     * @return
     */
    public static int getPriority(String op) {
        if ("+".equals(op) || "-".equals(op)) {
            return 1;
        }
        if ("*".equals(op) || "/".equals(op)) {
            return 2;
        }
        return 0;
    }

    /**
     * 将表达式按空格切割，并将分割出来的加到列表中
     *
     * @param express
     * @return
     */
    public List<String> getListBySplit(String express) {
        express = express.trim();
        String[] strArray = express.split(" ");
        List<String> expList = new ArrayList<>();
        for (String str : strArray) {
            expList.add(str);
        }
        return expList;
    }

    public static int calculate(List<String> expList) {
        ArrayStack3 stack = new ArrayStack3(12);
        for (String exp : expList) {
            if (exp.matches("\\d+")) {// 匹配数字
                stack.push(Integer.parseInt(exp));
            } else {// 如果是操作符，就弹出两次数字
                int num02 = stack.pop();// 先出栈的是后面的数字
                int num01 = stack.pop();
                char oper = exp.charAt(0);// 操作符就一位
                int result = stack.cal(num01, num02, oper);
                // 结果入栈
                stack.push(result);
            }

        }
        // 最后返回结果
        return stack.pop();
    }

}

class ArrayStack3 {
    /**
     * 栈的大小
     */
    private int maxSize;
    /**
     * 数组模拟栈，数据存放的地方
     */
    private int[] stack;
    /**
     * top表示栈顶，初始化为-1
     */
    private int top = -1;

    /**
     * 构造器
     */
    public ArrayStack3(int maxSize) {
        this.maxSize = maxSize;
        stack = new int[this.maxSize];
    }

    /**
     * 判断栈是否已满，如果栈中元素个数为0，即maxSize=0，此时栈既是满的也是空的
     */
    public boolean isFull() {
        return top == maxSize - 1;
    }

    /**
     * 判断栈是否为空
     */
    public boolean isEmpty() {
        return top == -1;
    }

    /**
     * 不为空返回true
     *
     * @return
     */
    public boolean isNotEmpty() {
        return !isEmpty();
    }

    /**
     * 入栈操作，入栈前要检验栈是否已满
     */
    public void push(int value) {
        if (isFull()) {
            System.out.println("栈已满，不能添加数据");
            return;
        }
        top++;
        stack[top] = value;
    }

    /**
     * 出栈，出栈前要判断栈是否为空
     */
    public int pop() {
        if (isEmpty()) {
            throw new RuntimeException("栈为空，无数据可取~");
        }
        int value = stack[top];
        top--;
        return value;
    }

    /**
     * 瞅一眼，不弹出
     *
     * @return
     */
    public int peek() {
        if (isEmpty()) {
            throw new RuntimeException("栈为空，无数据~");
        }
        return stack[top];
    }

    /**
     * 打印栈的数据，从栈顶到栈底的顺序
     */
    public void show() {
        if (isEmpty()) {
            System.out.println("栈空，无数据可显示~");
            return;
        }
        for (int i = top; i >= 0; i--) {
            System.out.printf("stack[%d]=%d\n", i, stack[i]);
        }
    }

    /**
     * 判断 c 是不是字符
     *
     * @param c
     * @return true - 表示是字符
     */
    public boolean isOper(char c) {
        return c == '+' || c == '-' || c == '*' || c == '/';
    }

    /**
     * 运算符的优先级
     *
     * @param c
     * @return
     */
    public int priority(int c) {
        if (c == '*' || c == '/') {
            return 1;
        } else if (c == '+' || c == '-') {
            return 0;
        } else {
            System.out.println("运算符错误");
            return -1;
        }
    }

    /**
     * 计算得到结果
     *
     * @param num1
     * @param num2
     * @param oper
     * @return
     */
    public int cal(int num1, int num2, int oper) {
        int res = 0;
        switch (oper) {
            case '+':
                res = num1 + num2;
                break;
            case '-':
                res = num1 - num2;
                break;
            case '*':
                res = num1 * num2;
                break;
            case '/':
                res = num1 / num2;
            default:
                break;

        }
        return res;
    }
}
